﻿package main

import (
	"fmt"
	"time"
)

func main() {
    e := elapse{time.Now()}
    list := read()
    t := e.get()
    fmt.Printf("n = %d, read = %s\n", len(list), t)
    fmt.Println("(method,time,result):")

    e.reset()
    res := findRepeat_1(list)
    t = e.get()
    fmt.Println("1", t, res)

    e.reset()
    res = findRepeat_2(list)
    t = e.get()
    fmt.Println("2", t, res)

    e.reset()
    res = findRepeat_4(list)
    t = e.get()
    fmt.Println("4", t, res)

    e.reset()
    res = findRepeat_3(list)
    t = e.get()
    fmt.Println("3", t, res)
}

//elapse
//count time elapsed
type elapse struct {
    start time.Time
}

func (e *elapse) reset() {
    e.start = time.Now()
}

func (e elapse) get() string {
    return fmt.Sprintf("%.6fs",
        time.Since(e.start).Seconds())
}

func read() []int {
    var n int
    fmt.Scan(&n)
    arr := make([]int, n)
    for i:=0; i<n; i++ {
        fmt.Scan(&arr[i])
    }
    return arr
}
////////////////////////////////////////////
//找出数组中唯一的重复元素
//
//详细描述见findrepeat.py

//结果统计
//以下时间不包括读取数据的时间
//n,time,readtime
// 1000001 0.004000s 7.567433s
//10000001 0.038002s 86.102925s
//Go的运算速度是C的两倍左右
//Go的读取标准控制台Scan速度是C的14倍左右
//以下是C的相应数据
// 1000001,0.002000s,0.537000s
//10000001,0.023000s,5.850000s
//
//多个算法比较
//n = 1000001, read = 7.263415s
//(method,time,result):
//1 0.004000s 965962
//2 0.000000s 965962
//4 0.023001s 965962
//3 0.018001s 965962

//解法一
//数组求和减去1-n的和
//缺点：当n很大时会出现溢出
func findRepeat_1(list []int) int {
    var sum uint64
    n := len(list)
    for i:=0; i<n; i++ {
        sum += uint64(list[i])
    }
    var un uint64 = uint64(n)
    un = sum - un*(un-1)/2
    return int(un)
}

//异或
func findRepeat_2(list []int) int {
    var r int
    for i, a := range list {
        r ^= a^i
    }
    return r
}

//图 标记
func findRepeat_3(list []int) int {
    var i int
    for {
        if list[i]<0 { break }
        list[i] = -list[i]
        i = -list[i]
    }
    return i
}

//图 步进
func findRepeat_4(list []int) int {
    s,f := 0,0
    for {
        s = list[s]
        f = list[list[f]]
        if s == f { break }
    }
    f = 0
    for {
        s = list[s]
        f = list[f]
        if s == f { break }
    }
    return s
}